package algorithm.dynamic;

/**
 * leetcode : https://leetcode.com/problems/minimum-path-sum/description/
 * Difficulty : Medium
 *
 * 给一个 M x N 的数组矩阵，求从左上角到右下角路径的最小和
 * 举栗：
 * Input:
 * [
 *  [1,3,1],
 *  [1,5,1],
 *  [4,2,1]
 * ]
 * Output : 7 (因为最短路径是1-3-1-1-1)
 *
 * 思路：
 * 动态规划，时间复杂度 O(N) N=m*n，m和n是矩阵的长和宽
 * 令矩阵中[0][0] 到 [x][y] 点的最短路径为 minPath([x][y])
 * 则由递推公式：
 * minPath([x][y]) = Math.min(minPath([x-1][y]) + grid[x][y], minPath([x][y]) + grid[x][y-1])
 *
 * 则到矩阵上任意一点的最短路径都可求得，时间复杂度: O(MxN) (M,N为矩阵的长和宽)
 *
 *
 * 回溯法，时间复杂度最差 O(M^N) 或者O(N^M) 指数级
 * （会执行超时）
 * 1) 记录一个目前已达的最短路径，在遍历的时候如果遇到比这个大就直接返回
 * 2) 如果比这个小，就继续往下，直到走到头，然后更新最小值。
 *
 * @Author Antony
 * @Since 2018/7/11 17:17
 */
public class MinimumPathSum {

    public static void main(String[] args) {
        int[] a = new int[]{1,3,1};
        int[] b = new int[]{1,5,1};
        int[] c = new int[]{4,2,1};
        int[][] grid = new int[][]{a,b,c};


        int[] a1 = new int[]{1,2,5};
        int[] b1 = new int[]{3,2,1};
        int[][] grid1 = new int[][]{a1,b1};

        int[][] g2 = new int[][]{{1}};

        System.out.println(minPathSum_BC(grid));
        System.out.println(minPathSum_DP(grid));

    }

    /**
     * 动态规划
     * (beats 99.4% - 5ms)
     */
    public static int minPathSum_DP(int[][] grid) {
        int width = grid[0].length;
        int height = grid.length;
        int[][] minDp = new int[height][width];
        int minUp, minLeft;
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                if(i==0 && j==0){
                    minDp[i][j] = grid[i][j];
                    continue;
                }else if(i==0){
                    minDp[i][j] = minDp[i][j-1] + grid[i][j];
                    continue;
                }else if(j==0){
                    minDp[i][j] = minDp[i-1][j] + grid[i][j];
                    continue;
                }
                minLeft = minDp[i][j-1];
                minUp = minDp[i-1][j];
                minDp[i][j] = minLeft < minUp ? minLeft + grid[i][j] : minUp + grid[i][j];
            }
        }

        return minDp[height-1][width-1];
    }


    /**
     * 回溯法
     * 执行超时，不可选
     */
    static int minPath =0;
    static int width=0;
    static int height=0;
    public static int minPathSum_BC(int[][] grid) {
        width = grid[0].length;
        height = grid.length;
        backTracing(0,0,0,grid);
        return minPath;
    }

    // 回溯法要注意，由于在一个边到顶以后还要回溯另一个边
    // 所以数组的临界条件不能越界, 也就是如下 w==width-1 && h==height-1
    // 相应的，递归的临界条件也应该使得下一层不能越界
    static void backTracing(int tmp, int h, int w, int[][] grid){
        tmp += grid[h][w];
        if(minPath !=0 && tmp >= minPath){
            return;
        }

        if(h==height-1 && w==width-1){
            minPath = minPath == 0 ? tmp : (tmp<minPath ? tmp : minPath);
            return;
        }

        if(h < height-1){    // 递归下一层不能越界
            backTracing(tmp, h+1, w, grid);
        }
        if(w < width-1){   // 递归下一层不能越界
            backTracing(tmp, h, w+1, grid);
        }
    }
}
